package Solution;

import java.util.HashMap;

import Data.ListNode;

public class Solution {
	// Two Sum
	// Given an array of integers, find two numbers such that they add up to a
	// specific target number.
	//
	// The function twoSum should return indices of the two numbers such that
	// they add up to the target, where index1 must be less than index2. Please
	// note that your returned answers (both index1 and index2) are not
	// zero-based.
	//
	// You may assume that each input would have exactly one solution.
	//
	// Input: numbers={2, 7, 11, 15}, target=9
	// Output: index1=1, index2=2
	public int[] twoSum(int[] numbers, int target) {
		HashMap<Integer, Integer> resultHashMap = new HashMap<Integer, Integer>();
		for (int i = 0; i < numbers.length; i++) {
			resultHashMap.put(numbers[i], i);
		}
		int index1 = -1;
		int index2 = -1;
		for (int i = 0; i < numbers.length; i++) {
			if (resultHashMap.get(target - numbers[i]) != null
					&& resultHashMap.get(target - numbers[i]) != i) {
				index1 = i;
				index2 = resultHashMap.get(target - numbers[i]);
				break;
			}
		}
		int[] result = new int[2];
		if (index1 > index2) {
			int t = index1;
			index1 = index2;
			index2 = t;
		}
		result[0] = index1 + 1;
		result[1] = index2 + 1;
		return result;
	}

	// Add Two Numbers
	// You are given two linked lists representing two non-negative numbers. The
	// digits are stored in reverse order and each of their nodes contain a
	// single digit. Add the two numbers and return it as a linked list.
	//
	// Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
	// Output: 7 -> 0 -> 8
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		int carry = 0;

		ListNode p1, p2, temp;
		ListNode p3 = new ListNode(0);
		p1 = l1;
		p2 = l2;
		temp = p3;

		while (p1 != null || p2 != null) {
			if (p1 != null) {
				carry += p1.val;
				p1 = p1.next;
			}
			if (p2 != null) {
				carry += p2.val;
				p2 = p2.next;
			}
			p3.next = new ListNode(carry % 10);
			p3 = p3.next;
			carry /= 10;
		}
		if (carry == 1) {
			p3.next = new ListNode(carry);
		}

		return temp.next;

	}

	// Longest Substring Without Repeating Characters
	// Given a string, find the length of the longest substring without
	// repeating characters. For example, the longest substring without
	// repeating letters for "abcabcbb" is "abc", which the length is 3. For
	// "bbbbb" the longest substring is "b", with the length of 1.
	public static int lengthOfLongestSubstring2(String s) {
		char[] str = s.toCharArray();
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		int result = 0;
		int sum = 0;
		for (int i = 0; i < str.length; i++) {
			sum++;
			if (!map.containsKey(str[i])) {
				map.put(str[i], i);
			} else {
				result = Math.max(map.size(), result);
				i = map.get(str[i]);
				map.clear();
			}
		}

		System.out.println("sum:" + sum);
		return Math.max(map.size(), result);
	}

	public static int lengthOfLongestSubstring(String s) {
		char[] str = s.toCharArray();
		boolean[] flag = new boolean[256];
		int result = 0;
		int start = 0;
		for (int i = 0; i < str.length; i++) {
			if (!flag[str[i]]) {
				flag[str[i]] = true;
			} else {
				result = Math.max(result, i - start);
				for (int j = start; j < i; j++) {
					if (str[i] == str[j]) {
						start = j + 1;
						break;
					}
					flag[str[j]] = false;
				}
			}
		}

		return Math.max(result, str.length - start);
	}

	// Median of Two Sorted Arrays
	// There are two sorted arrays A and B of size m and n respectively. Find
	// the median of the two sorted arrays. The overall run time complexity
	// should be O(log (m+n)).
    //	如果A[k/2-1]<B[k/2-1]，那么A[0]~A[k/2-1]一定在第k小的数的序列当中
	
	public static int findKth(int A[],int B[],int k,int aHead,int aTail,int bHead,int bTail){
		int aLen=aTail-aHead+1;
		int bLen=bTail-bHead+1;
		if(k==0){
			return Math.min(A[aHead], B[bHead]);
		}
		if(aLen==0){
			
		}
		if(bLen==0){
			
		}
		
		return 0;
	}
	
	public static double findMedianSortedArrays(int A[], int B[]) {
		int aLen=A.length;
		int bLen=B.length;
		//0,1,2,3:4/2=2,4/2-1=1->1,2
		//0,1,2,3,4:5/2=2
		if((aLen+bLen)%2==0){
			return (findKth(A, B, (aLen+bLen)/2, 0, aLen-1, 0, bLen-1)+
					 findKth(A, B, (aLen+bLen)/2-1, 0, aLen-1, 0, bLen-1))*0.5;
		}
		else{
			return findKth(A, B, (aLen+bLen)/2, 0, aLen-1, 0, bLen-1);
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
//		String s = "pwwkew";
//		// String s="AAAA";
//		System.out.println(lengthOfLongestSubstring(s));
		
		

	}

}
